/**
 * 
 */
package problem;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *  问题描述：列出小于数n的所有质数。
 *  Eratosthenes篩選求質數：
 *  	1. 将2的倍数筛选掉
 *  	2. 将3的倍数筛选掉。
 *  	。。。。
 *  	3. 依此类推。
 *  注：檢查的次數還可以再減少，事實上，只要檢查6n+1與6n+5就可以了，
 *  也就是直接跳過2與3的倍數，使得程式中的if的檢查動作可以減少。
 * @author Jun
 *
 */
public class Prime {

	 public static List<Integer> findPrimes(int max) {
	        int[] prime = new int[max+1]; 
	        Arrays.fill(prime, 1);

	        for(int i = 2; i*i <= max; i++) { 
	            if(prime[i] == 1) { 
	                for(int j = 2*i; j <= max; j++) { 
	                    if(j % i == 0) 
	                        prime[j] = 0;  
	                } 
	            } 
	        } 

	        List<Integer> list = new ArrayList<Integer>();
	        for(int i = 2; i <= max; i++) { 
	            if(prime[i] == 1) { 
	                list.add(i); 
	            } 
	        }
	        
	        return list;
	    }
	    
	    public static void main(String[] args) {
	        for(Integer p : Prime.findPrimes(1000)) {
	            System.out.print(p + " ");
	        }
	    }
}
